# -*- coding: utf-8 -*-
# @Time: 2021/8/17 8:56
# @File: problem-101.py
# @DESC: https://leetcode-cn.com/problems/symmetric-tree/
# 判断树是否位对称结构：用两个指针记录，分别遍历左右两个子树

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:

    def check(self, p, q):
        if p == q == None:
            return True
        if p == None or q == None:
            return False
        return p.val == q.val and self.check(p.right, q.left) and self.check(p.left, q.right)

    def isSymmetric(self, root: TreeNode) -> bool:
        return self.check(root, root)


# 思路，左右两边对应位置的节点相等，可以采递归的方式遍历根目录下左右节点的值，再比较值是否相等


root = TreeNode(1)

root.left = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)

root.right = TreeNode(2)
root.right.right = TreeNode(3)
root.right.left = TreeNode(4)

S = Solution()
result = S.isSymmetric(root)

print(result)
